import java.lang.*;
import java.util.*;
import java.io.*;

import org.apache.commons.collections.*;

public class DrawArch 
{
	class Forest
	{
		private LinkedList<Forest> parents = null;
		private LinkedList<Forest> kids = null;
		
		private String projName = null;
		
		int layer = -1;
		
		private boolean visitied = false;
		
		public Forest(String projName)
		{
			parents = new LinkedList<Forest>();
			kids = new LinkedList<Forest>();
			
			this.projName = projName;
		}
		
		public void adopKid(Forest kid)
		{
			kids.add(kid);
		}
		
		public void followParent(Forest parent)
		{
			parents.add(parent);
		}
		
		public void setVisitFlagTrue()
		{
			visitied = true;
		}
		
		public void setVisitFlagFalse()
		{
			visitied = false;
		}
		
		public void dfsTraverse(HashSet<String> parentProjSet)
		{
			
			visitied = true;
			
			parentProjSet.add(this.projName);
			
			
			int count = 0;
			
			if (kids.size() > 0)
			{
				//System.out.println(projName + " parents begin");
				for (Forest kid: kids)
				{
					if (kid.visitied == false)
					{
						kid.dfsTraverse(parentProjSet);
					}
				}
				//System.out.println(projName + " parents end");
			}

		}
		
		public int inverseDfsTraverse(HashSet<String> parentProjSet)
		{
			
			
			visitied = true;
			
			parentProjSet.add(this.projName);
			
			
			int count = 0;
			
			if (parents.size() > 0)
			{
				//System.out.println(projName + " parents begin");
				for (Forest parent: parents)
				{
					if (parent.visitied == false)
					{
						count += parent.inverseDfsTraverse(parentProjSet);
					}
				}
				//System.out.println(projName + " parents end");
			}
			
			return count + 1;
		}
	}
	
	LinkedList<Forest> bulk = null;
	
	public DrawArch()
	{
		bulk = new LinkedList<Forest>();
	}
	
	void loadForest(String proj2ProjMapFile) throws IOException
	{
		//load from file
		MultiHashMap proj2ProjMap = new MultiHashMap();
		Utilities.readMultiMapFromFile(proj2ProjMap, proj2ProjMapFile);
		
		
		HashMap<String, Forest> projNameLocationMap = new HashMap<String, Forest>();
		
		for (String proj: (Set<String>)proj2ProjMap.keySet())
		{
			Forest parent = null;
			
			if (projNameLocationMap.containsKey(proj) == false)
			{
				parent = new Forest(proj);
				
				projNameLocationMap.put(proj, parent);
				bulk.add(parent);
			}
			else
			{
				parent = projNameLocationMap.get(proj);
			}
			
			for (String basedProj: (Collection<String>) proj2ProjMap.get(proj))
			{
				Forest kid = null;
				
				if (projNameLocationMap.containsKey(basedProj) == false)
				{
					kid = new Forest(basedProj);
					
					projNameLocationMap.put(basedProj, kid);
					bulk.add(kid);
				}
				else
				{
					kid = projNameLocationMap.get(basedProj);
				}
				
				parent.adopKid(kid);
				kid.followParent(parent);
			}
		}	
	}
	
	private void setAllVisited()
	{
		for (Forest node: bulk)
		{
			node.setVisitFlagTrue();
		}
	}
	
	private void setAllNotVisited()
	{
		for (Forest node: bulk)
		{
			node.setVisitFlagFalse();
		}
	}
	
	private HashSet<Forest> findRoot()
	{
		HashSet<Forest> rootList = new HashSet<Forest>();
		
		for (Forest node: bulk)
		{
			if (node.parents.size() == 0)
			{
				rootList.add(node);
			}
		}
		
		return rootList;
	}
	
	private HashSet<Forest>  findBottom()
	{
		HashSet<Forest> bottomSet = new HashSet<Forest>();
		
		for (Forest node: bulk)
		{
			if (node.kids.size() == 0)
			{
				bottomSet.add(node);
			}
		}
		
		return bottomSet;
	}
	
	public void dfsTraverse()
	{
		HashSet<Forest> topList = findRoot();
		int count = 0;
		HashSet<String> parentProjSet = new HashSet<String>();
		
		for (Forest node: topList)
		{
			System.out.println("-----------bottom------------");
			node.inverseDfsTraverse(parentProjSet);
		}
	}
	
	private int inverseDfsTraverse()
	{
		
		HashSet<Forest> bottomList = findBottom();
		int count = 0;
		HashSet<String> parentProjSet = new HashSet<String>();
		
		for (Forest node: bottomList)
		{
			System.out.println("-----------bottom------------");
			node.inverseDfsTraverse(parentProjSet);
		}
		
		
		return count;
	}
	
	private void getInfluentialData(String influentialDataFile) throws IOException
	{
		
		int min = 99999999;
		int max = -1;
		
		int minKidNum = 99999999;
		int maxKidNum = -1;
		
		int minParentNum = 99999999;
		int maxParentNum = -1;
		
		double ave = 0.0;
		
		double aveParentNum = 0.0;
		double aveKidNum = 0.0;
		
		HashSet<String> parentProjSet = new HashSet<String>();
		
		HashMap<String, String> influentialDataMap = new HashMap<String, String>();
		
		for (Forest node: bulk)
		{
			setAllNotVisited();
			
			parentProjSet.clear();
			node.inverseDfsTraverse(parentProjSet);
			
			influentialDataMap.put(node.projName, Integer.toString(parentProjSet.size()));
			
			if (max < parentProjSet.size())
			{
				max = parentProjSet.size();
			}
			
			if (min > parentProjSet.size())
			{
				min = parentProjSet.size();
			}
			
			
			if (maxKidNum < node.kids.size())
			{
				maxKidNum = node.kids.size();
			}
			
			if (minKidNum > node.kids.size())
			{
				minKidNum = node.kids.size();
			}
			
			if (maxParentNum < node.parents.size())
			{
				maxParentNum = node.parents.size();
			}
			
			if (minParentNum > node.parents.size())
			{
				minParentNum = node.parents.size();
			}
			
			
			ave += parentProjSet.size();
			aveKidNum += node.kids.size();
			aveParentNum += node.parents.size();
		}
		
		System.out.println("ave: " + ave/bulk.size());
		System.out.println("max: " + max);
		System.out.println("min: " + min);
		
		System.out.println("ave parents: " + aveParentNum/bulk.size());
		System.out.println("max parents: " + maxParentNum);
		System.out.println("min parents: " + minParentNum);
		
		System.out.println("ave kids: " + aveKidNum/bulk.size());
		System.out.println("max kids: " + maxKidNum);
		System.out.println("min kids: " + minKidNum);
		
		Utilities.writeMapToFile(influentialDataMap, influentialDataFile);
		
	}
	
	private void getdependencyData(String dependencyDataMapFile) throws IOException
	{
		
		int min = 99999999;
		int max = -1;
		
		int minKidNum = 99999999;
		int maxKidNum = -1;
		
		int minParentNum = 99999999;
		int maxParentNum = -1;
		
		double ave = 0.0;
		
		double aveParentNum = 0.0;
		double aveKidNum = 0.0;
		
		HashSet<String> parentProjSet = new HashSet<String>();
		
		HashMap<String, String> dependencyDataMap = new HashMap<String, String>();
		
		for (Forest node: bulk)
		{
			setAllNotVisited();
			
			parentProjSet.clear();
			node.dfsTraverse(parentProjSet);
			
			dependencyDataMap.put(node.projName, Integer.toString(parentProjSet.size()));
			
			if (max < parentProjSet.size())
			{
				max = parentProjSet.size();
			}
			
			if (min > parentProjSet.size())
			{
				min = parentProjSet.size();
			}
			
			
			if (maxKidNum < node.kids.size())
			{
				maxKidNum = node.kids.size();
			}
			
			if (minKidNum > node.kids.size())
			{
				minKidNum = node.kids.size();
			}
			
			if (maxParentNum < node.parents.size())
			{
				maxParentNum = node.parents.size();
			}
			
			if (minParentNum > node.parents.size())
			{
				minParentNum = node.parents.size();
			}
			
			
			ave += parentProjSet.size();
			aveKidNum += node.kids.size();
			aveParentNum += node.parents.size();
		}
		
		System.out.println("ave: " + ave/bulk.size());
		System.out.println("max: " + max);
		System.out.println("min: " + min);
		
		System.out.println("ave parents: " + aveParentNum/bulk.size());
		System.out.println("max parents: " + maxParentNum);
		System.out.println("min parents: " + minParentNum);
		
		System.out.println("ave kids: " + aveKidNum/bulk.size());
		System.out.println("max kids: " + maxKidNum);
		System.out.println("min kids: " + minKidNum);
		
		Utilities.writeMapToFile(dependencyDataMap, dependencyDataMapFile);
		
	}
	
	public void getTopBottom()
	{
		HashSet<Forest> rootList = findRoot();
	
		
		System.out.println("---------- Top Projs -----------");
		for (Forest node: rootList)
		{
			System.out.println(node.projName);
		}
		
		HashSet<Forest> bottomSet = findBottom();
		
		System.out.println("---------- Boottom Projs -----------");
		for (Forest node: bottomSet)
		{
			System.out.println(node.projName);
		}
	}
	
	public void initFlowFile(String proj2ProjMapFile, String flowNodeMapFile, String inverseNodeIDMapFile) 
		throws IOException
	{
		MultiHashMap proj2ProjMap = new MultiHashMap();
		Utilities.readMultiMapFromFile(proj2ProjMap, proj2ProjMapFile);
		
		HashSet<Forest> rootSet = findRoot();
		
		MultiHashMap advProj2ProjMap = new MultiHashMap();
		
		for (Forest node: rootSet)
		{
			advProj2ProjMap.put("source", node.projName + "_first");
		}
		
		HashSet<Forest> bottomSet = findRoot();
		
		for (Forest node: bottomSet)
		{
			advProj2ProjMap.put(node.projName + "_second", "sink");
		}
		
		HashSet<String> projSet = new HashSet<String>();
		for (String proj: (Set<String>)proj2ProjMap.keySet())
		{
			projSet.add(proj);
			for (String basedProj: (Collection<String>)proj2ProjMap.get(proj))
			{
				projSet.add(basedProj);
			}
		}
		
		for (String proj: projSet)
		{
			advProj2ProjMap.put(proj + "_first", proj + "_second");
		}
		
		for (String proj: (Set<String>)proj2ProjMap.keySet())
		{
			for (String basedProj: (Collection<String>)proj2ProjMap.get(proj))
			{
				advProj2ProjMap.put(proj + "_second", basedProj + "_first");
			}
		}
		
		HashMap<String, Integer> nodeIDMap = new HashMap<String, Integer>();
		projSet.clear();
		
		HashMap<String, String> inverseNodeIDMap = new HashMap<String, String>();
		
		for (String srcNodeName: (Set<String>) advProj2ProjMap.keySet())
		{
			projSet.add(srcNodeName);
		}
		
		for (String dstNodeName: (Collection<String>) advProj2ProjMap.values())
		{
			projSet.add(dstNodeName);
		}
		
		nodeIDMap.put("source", 0);
		nodeIDMap.put("sink", 1);
		
		inverseNodeIDMap.put(Integer.toString(0), "source");
		inverseNodeIDMap.put(Integer.toString(1), "sink");
		
		int nodeID = 2;
		
		for (String proj: projSet)
		{
			if (proj.equals("source") || proj.equals("sink"))
			{
				continue;
			}
			
			nodeIDMap.put(proj, nodeID);
			inverseNodeIDMap.put(Integer.toString(nodeID), proj);
			nodeID++;
		}
		
		DataOutputStream out = new DataOutputStream(new FileOutputStream(flowNodeMapFile));
		
		
		out.writeInt(projSet.size());
		out.writeInt(advProj2ProjMap.totalSize());
		
		for (String proj: (Set<String>)advProj2ProjMap.keySet())
		{
			for (String basedProj: (Collection<String>)advProj2ProjMap.get(proj))
			{
				out.writeInt(nodeIDMap.get(proj));
				out.writeInt(nodeIDMap.get(basedProj));
				
				out.writeDouble((Double)(1.0));
			}
		}
		
		out.close();
		
		Utilities.writeMapToFile(inverseNodeIDMap, inverseNodeIDMapFile);
		
	}

	public void getMinCut(String flowNodeMapFile, String inverseIDMapFile) throws IOException
	{
		HashMap<String, String> inverseNodeIDMap = new HashMap<String, String>();
		Utilities.readMapFromFile(inverseNodeIDMap, inverseIDMapFile);
		
	  FileInputStream fstream = new FileInputStream(flowNodeMapFile);
	  // Get the object of DataInputStream
	  DataInputStream in = new DataInputStream(fstream);
	  
	  System.out.println("----------");
	  
	  FlowNetwork G = new FlowNetwork(in);
      System.out.println(G);
		
      
      int s = 0;
      int t = 1;
      
      // compute maximum flow and minimum cut
      FordFulkerson maxflow = new FordFulkerson(G, s, t);
      System.out.println("Max flow from " + s + " to " + t);
      for (int v = 0; v < G.V(); v++) {
          for (FlowEdge e : G.adj(v)) {
              if ((v == e.from()) && e.flow() > 0)
              	System.out.println("   " + e);
          }
      }

      HashSet<String> minCutProjSet = new HashSet<String>();
      
      // print min-cut
      System.out.print("Min cut: ");
      for (int v = 0; v < G.V(); v++) {
          if (maxflow.inCut(v)) 
          { 
        	 //System.out.print(v + " ");
          
        	 minCutProjSet.add(inverseNodeIDMap.get(Integer.toString(v)));
          }
      }
      System.out.println();

      //System.out.println("Max flow value = " +  maxflow.value());	
      
      for (String minCutProj: minCutProjSet)
      {
    	  System.out.println(minCutProj);
      }
		
      in.close();
	}
	
	public static void main(String args[]) throws IOException
	{
		DrawArch fuyun = new DrawArch();
		fuyun.loadForest("data/android-4.0.1/proj2ProjMap.csv");
		
		fuyun.getInfluentialData("data/android-4.0.1/influentialMap.csv");
		
		fuyun.getdependencyData("data/android-4.0.1/dependencyDataMap.csv");
		
		//fuyun.getTopBottom();
		
		//fuyun.initFlowFile("data/android-4.0.1/proj2ProjMap.csv", 
				//"data/android-4.0.1/flowNodeMap.csv",
				//"data/android-4.0.1/inverseIDMap.csv");
		//fuyun.getMinCut("data/android-4.0.1/flowNodeMap.csv",
				//"data/android-4.0.1/inverseIDMap.csv");
	}
}
